{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Sum of Total Strength of Wizards"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #array #prefix-sum #monotonic-stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #数组 #前缀和 #单调栈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: totalStrength"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #巫师的总力量和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>作为国王的统治者，你有一支巫师军队听你指挥。</p>\n",
    "\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始的整数数组&nbsp;<code>strength</code>&nbsp;，其中&nbsp;<code>strength[i]</code>&nbsp;表示第&nbsp;<code>i</code>&nbsp;位巫师的力量值。对于连续的一组巫师（也就是这些巫师的力量值是&nbsp;<code>strength</code>&nbsp;的&nbsp;<strong>子数组</strong>），<strong>总力量</strong>&nbsp;定义为以下两个值的&nbsp;<strong>乘积</strong>&nbsp;：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>巫师中 <strong>最弱</strong>&nbsp;的能力值。</li>\n",
    "\t<li>组中所有巫师的个人力量值 <strong>之和</strong>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回 <strong>所有</strong>&nbsp;巫师组的 <strong>总</strong>&nbsp;力量之和。由于答案可能很大，请将答案对&nbsp;<code>10<sup>9</sup> + 7</code>&nbsp;<strong>取余</strong>&nbsp;后返回。</p>\n",
    "\n",
    "<p><strong>子数组</strong>&nbsp;是一个数组里 <strong>非空</strong>&nbsp;连续子序列。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>strength = [1,3,1,2]\n",
    "<b>输出：</b>44\n",
    "<b>解释：</b>以下是所有连续巫师组：\n",
    "- [<em><strong>1</strong></em>,3,1,2] 中 [1] ，总力量值为 min([1]) * sum([1]) = 1 * 1 = 1\n",
    "- [1,<em><strong>3</strong></em>,1,2] 中 [3] ，总力量值为 min([3]) * sum([3]) = 3 * 3 = 9\n",
    "- [1,3,<em><strong>1</strong></em>,2] 中 [1] ，总力量值为 min([1]) * sum([1]) = 1 * 1 = 1\n",
    "- [1,3,1,<em><strong>2</strong></em>] 中 [2] ，总力量值为 min([2]) * sum([2]) = 2 * 2 = 4\n",
    "- [<em><strong>1,3</strong></em>,1,2] 中 [1,3] ，总力量值为 min([1,3]) * sum([1,3]) = 1 * 4 = 4\n",
    "- [1,<em><strong>3,1</strong></em>,2] 中 [3,1] ，总力量值为 min([3,1]) * sum([3,1]) = 1 * 4 = 4\n",
    "- [1,3,<em><strong>1,2</strong></em>] 中 [1,2] ，总力量值为 min([1,2]) * sum([1,2]) = 1 * 3 = 3\n",
    "- [<em><strong>1,3,1</strong></em>,2] 中 [1,3,1] ，总力量值为 min([1,3,1]) * sum([1,3,1]) = 1 * 5 = 5\n",
    "- [1,<em><strong>3,1,2</strong></em>] 中 [3,1,2] ，总力量值为 min([3,1,2]) * sum([3,1,2]) = 1 * 6 = 6\n",
    "- [<em><strong>1,3,1,2</strong></em>] 中 [1,3,1,2] ，总力量值为 min([1,3,1,2]) * sum([1,3,1,2]) = 1 * 7 = 7\n",
    "所有力量值之和为 1 + 9 + 1 + 4 + 4 + 4 + 3 + 5 + 6 + 7 = 44 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>strength = [5,4,6]\n",
    "<b>输出：</b>213\n",
    "<b>解释：</b>以下是所有连续巫师组：\n",
    "- [<em><strong>5</strong></em>,4,6] 中 [5] ，总力量值为 min([5]) * sum([5]) = 5 * 5 = 25\n",
    "- [5,<em><strong>4</strong></em>,6] 中 [4] ，总力量值为 min([4]) * sum([4]) = 4 * 4 = 16\n",
    "- [5,4,<em><strong>6</strong></em>] 中 [6] ，总力量值为 min([6]) * sum([6]) = 6 * 6 = 36\n",
    "- [<em><strong>5,4</strong></em>,6] 中 [5,4] ，总力量值为 min([5,4]) * sum([5,4]) = 4 * 9 = 36\n",
    "- [5,<em><strong>4,6</strong></em>] 中 [4,6] ，总力量值为 min([4,6]) * sum([4,6]) = 4 * 10 = 40\n",
    "- [<em><strong>5,4,6</strong></em>] 中 [5,4,6] ，总力量值为 min([5,4,6]) * sum([5,4,6]) = 4 * 15 = 60\n",
    "所有力量值之和为 25 + 16 + 36 + 36 + 40 + 60 = 213 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= strength.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= strength[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [sum-of-total-strength-of-wizards](https://leetcode.cn/problems/sum-of-total-strength-of-wizards/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [sum-of-total-strength-of-wizards](https://leetcode.cn/problems/sum-of-total-strength-of-wizards/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,3,1,2]', '[5,4,6]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalStrength(self, nums: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n = len(nums)\n",
    "        left = [0] * n\n",
    "        right = [0] * n\n",
    "        stk = []\n",
    "        for i in range(n):\n",
    "            while stk and nums[i] < nums[stk[-1]]:\n",
    "                stk.pop()\n",
    "            if stk:\n",
    "                left[i] = stk[-1]\n",
    "            else:\n",
    "                left[i] = -1\n",
    "            stk.append(i)\n",
    "        stk = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while stk and nums[i] <= nums[stk[-1]]:\n",
    "                stk.pop()\n",
    "            if stk:\n",
    "                right[i] = stk[-1]\n",
    "            else:\n",
    "                right[i] = n\n",
    "            stk.append(i)\n",
    "        ans = 0\n",
    "        ss = list(accumulate(accumulate(nums, initial=0), initial=0))  # 前缀和的前缀和\n",
    "        for i in range(n):\n",
    "            l, r = left[i] + 1, right[i] - 1\n",
    "            ans += ((i - l + 1) * (ss[r + 2] - ss[i + 1]) - (r - i + 1) * (ss[i + 1] - ss[l])) * nums[i]\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalStrength(self, strength: List[int]) -> int:\n",
    "        stk = []\n",
    "        n = len(strength)\n",
    "        left = [-1] * n\n",
    "        right = [n] * n\n",
    "        for i in range(n):\n",
    "            while stk and strength[stk[-1]] >= strength[i]:\n",
    "                right[stk.pop()] = i\n",
    "            if stk:\n",
    "                left[i] = stk[-1]\n",
    "            stk.append(i)\n",
    "\n",
    "        s = accumulate(strength, initial=1)\n",
    "        ss = list(accumulate(s, initial=0))\n",
    "\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            l, r = left[i] + 1, right[i] - 1\n",
    "            res += ((i-l+1) * (ss[r+2] - ss[i+1]) - (r-i+1) * (ss[i+1] - ss[l])) * strength[i]\n",
    "\n",
    "        return res % (10 ** 9 + 7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import accumulate\n",
    "class Solution:\n",
    "    def totalStrength(self, strength: List[int]) -> int:\n",
    "        n=len(strength)\n",
    "        left,right,st=[-1]*n,[n]*n,[]\n",
    "        for i,v in enumerate(strength):\n",
    "            while st and strength[st[-1]]>=v:\n",
    "                right[st.pop()]=i\n",
    "            if st:\n",
    "                left[i]=st[-1]\n",
    "            st.append(i)\n",
    "        ss=list(accumulate(accumulate(strength,initial=0),initial=0))\n",
    "\n",
    "        ans=0\n",
    "        for i,v in enumerate(strength):\n",
    "            l,r=left[i]+1,right[i]-1\n",
    "            tot=(i-l+1)*(ss[r+2]-ss[i+1])-(r-i+1)*(ss[i+1]-ss[l])\n",
    "            ans+=v*tot\n",
    "        return ans%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalStrength(self, strength: List[int]) -> int:\n",
    "        n = len(strength)\n",
    "\n",
    "        # left[i] 为左侧严格小于 strength[i] 的最近元素位置（不存在时为 -1）\n",
    "        # right[i] 为右侧小于等于 strength[i] 的最近元素位置（不存在时为 n）\n",
    "        left = [-1] * n\n",
    "        right = [n] * n\n",
    "        st = []\n",
    "\n",
    "        for i, v in enumerate(strength):\n",
    "            while st and strength[st[-1]] >= v:\n",
    "                right[st.pop()] = i\n",
    "            if st:\n",
    "                left[i] = st[-1]\n",
    "            st.append(i)\n",
    "\n",
    "        ss = list(accumulate(accumulate(strength, initial=0), initial=0))  # 前缀和的前缀和\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        for i, v in enumerate(strength):\n",
    "            l, r = left[i] + 1, right[i] - 1  # [l, r]  左闭右闭\n",
    "            tot = (i - l + 1) * (ss[r + 2] - ss[i + 1]) - (r - i + 1) * (ss[i + 1] - ss[l])\n",
    "            ans += v * tot  # 累加贡献\n",
    "\n",
    "        return ans % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalStrength(self, a: List[int]) -> int:\n",
    "        n = len(a)\n",
    "        left = [-1] * n\n",
    "        right = [n] * n\n",
    "        st = []\n",
    "\n",
    "        for i, v in enumerate(a):\n",
    "            while st and a[st[-1]] >= v:\n",
    "                right[st.pop()] = i \n",
    "            if st:\n",
    "                left[i] = st[-1]\n",
    "            st.append(i)\n",
    "        \n",
    "        s = accumulate(a, initial=0)\n",
    "        ss = list(accumulate(s, initial=0))\n",
    "\n",
    "        ans = 0 \n",
    "        for i, v in enumerate(a):\n",
    "            l, r = left[i] + 1, right[i] - 1 \n",
    "            tot = (i - l + 1) * (ss[r + 2] - ss[i + 1]) - (r - i + 1) * (ss[i + 1] - ss[l])\n",
    "            ans += v * tot \n",
    "        return ans % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import accumulate\n",
    "class Solution:\n",
    "    def totalStrength(self, strength: List[int]) -> int:\n",
    "        n=len(strength)\n",
    "        left,right,st=[-1]*n,[n]*n,[]\n",
    "        for i,v in enumerate(strength):\n",
    "            while st and strength[st[-1]]>=v:\n",
    "                right[st.pop()]=i\n",
    "            if st:\n",
    "                left[i]=st[-1]\n",
    "            st.append(i)\n",
    "        ss=list(accumulate(accumulate(strength,initial=0),initial=0))\n",
    "\n",
    "        ans=0\n",
    "        for i,v in enumerate(strength):\n",
    "            l,r=left[i]+1,right[i]-1\n",
    "            tot=(i-l+1)*(ss[r+2]-ss[i+1])-(r-i+1)*(ss[i+1]-ss[l])\n",
    "            ans+=v*tot\n",
    "        return ans%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalStrength(self, strength: List[int]) -> int:\n",
    "        mod=10**9+7\n",
    "        prefix=list(accumulate(accumulate(strength,initial=0),initial=0))\n",
    "        stk=[]\n",
    "        pre,suf=[-1]*len(strength),[len(strength)]*len(strength)\n",
    "        for i in range(len(strength)):\n",
    "            while stk and strength[i]<=strength[stk[-1]]:\n",
    "                suf[stk.pop()]=i\n",
    "            if stk: pre[i]=stk[-1]\n",
    "            stk.append(i)\n",
    "        res=0\n",
    "        for i in range(len(strength)):\n",
    "            s=(prefix[suf[i]+1]-prefix[i+1])*(i-pre[i])-(prefix[i+1]-prefix[pre[i]+1])*(suf[i]-i)\n",
    "            res+=strength[i]*s\n",
    "        return res%mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalStrength(self, a: List[int]) -> int:\n",
    "        n = len(a)\n",
    "\n",
    "        left = [-1] * n\n",
    "        right = [n] * n\n",
    "        st = []\n",
    "        for i, v in enumerate(a):\n",
    "            while st and a[st[-1]] >= v:\n",
    "                right[st.pop()] = i\n",
    "            if st :\n",
    "                left[i] = st[-1]\n",
    "            st.append(i)\n",
    "            \n",
    "        ss = list(accumulate(accumulate(a, initial = 0), initial = 0))\n",
    "        ans = 0\n",
    "        for i, v in enumerate(a):\n",
    "            L, R = left[i] + 1, right[i] - 1\n",
    "            tot = (i-L+1)*(ss[R+2]-ss[i+1]) - (R-i+1)*(ss[i+1]-ss[L])\n",
    "            ans += v*tot\n",
    "        return ans %(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalStrength(self, strength: List[int]) -> int:\n",
    "        n = len(strength)\n",
    "        # left[i] 为左侧严格小于 strength[i] 的最近元素位置（不存在时为 -1）\n",
    "        # right[i] 为右侧小于等于 strength[i] 的最近元素位置（不存在时为 n）\n",
    "        left, right, st = [-1] * n, [n] * n, []\n",
    "        for i, v in enumerate(strength):\n",
    "            while st and strength[st[-1]] >= v: right[st.pop()] = i\n",
    "            if st: left[i] = st[-1]\n",
    "            st.append(i)\n",
    "\n",
    "        ss = list(accumulate(accumulate(strength, initial=0), initial=0))  # 前缀和的前缀和\n",
    "\n",
    "        ans = 0\n",
    "        for i, v in enumerate(strength):\n",
    "            l, r = left[i] + 1, right[i] - 1  # [l, r]  左闭右闭\n",
    "            tot = (i - l + 1) * (ss[r + 2] - ss[i + 1]) - (r - i + 1) * (ss[i + 1] - ss[l])\n",
    "            ans += v * tot  # 累加贡献\n",
    "        return ans % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalStrength(self, strength: List[int]) -> int:\n",
    "        n = len(strength)\n",
    "        # left[i] 为左侧严格小于 strength[i] 的最近元素位置（不存在时为 -1）\n",
    "        # right[i] 为右侧小于等于 strength[i] 的最近元素位置（不存在时为 n）\n",
    "        left, right, st = [-1] * n, [n] * n, []\n",
    "        for i, v in enumerate(strength):\n",
    "            while st and strength[st[-1]] >= v: right[st.pop()] = i\n",
    "            if st: left[i] = st[-1]\n",
    "            st.append(i)\n",
    "\n",
    "        ss = list(accumulate(accumulate(strength, initial=0), initial=0))  # 前缀和的前缀和\n",
    "\n",
    "        ans = 0\n",
    "        for i, v in enumerate(strength):\n",
    "            l, r = left[i] + 1, right[i] - 1  # [l, r]  左闭右闭\n",
    "            tot = (i - l + 1) * (ss[r + 2] - ss[i + 1]) - (r - i + 1) * (ss[i + 1] - ss[l])\n",
    "            ans += v * tot  # 累加贡献\n",
    "        return ans % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def totalStrength(self, strength: List[int]) -> int:\n",
    "\n",
    "        n = len(strength)\n",
    "\n",
    "        # left[i] 为左侧严格小于 strength[i] 的最近元素位置（不存在时为 -1）\n",
    "\n",
    "        # right[i] 为右侧小于等于 strength[i] 的最近元素位置（不存在时为 n）\n",
    "\n",
    "        left, right, st = [-1] * n, [n] * n, []\n",
    "\n",
    "        for i, v in enumerate(strength):\n",
    "\n",
    "            while st and strength[st[-1]] >= v: right[st.pop()] = i\n",
    "\n",
    "            if st: left[i] = st[-1]\n",
    "\n",
    "            st.append(i)\n",
    "\n",
    "\n",
    "\n",
    "        ss = list(accumulate(accumulate(strength, initial=0), initial=0))  # 前缀和的前缀和\n",
    "\n",
    "\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        for i, v in enumerate(strength):\n",
    "\n",
    "            l, r = left[i] + 1, right[i] - 1  # [l, r]  左闭右闭\n",
    "\n",
    "            tot = (i - l + 1) * (ss[r + 2] - ss[i + 1]) - (r - i + 1) * (ss[i + 1] - ss[l])\n",
    "\n",
    "            ans += v * tot  # 累加贡献\n",
    "\n",
    "        return ans % (10 ** 9 + 7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalStrength(self, strength: List[int]) -> int:\n",
    "        n = len(strength)\n",
    "        # left[i] 为左侧严格小于 strength[i] 的最近元素位置（不存在时为 -1）\n",
    "        # right[i] 为右侧小于等于 strength[i] 的最近元素位置（不存在时为 n）\n",
    "        left, right, st = [-1] * n, [n] * n, []\n",
    "        for i, v in enumerate(strength):\n",
    "            while st and strength[st[-1]] >= v: right[st.pop()] = i\n",
    "            if st: left[i] = st[-1]\n",
    "            st.append(i)\n",
    "\n",
    "        ss = list(accumulate(accumulate(strength, initial=0), initial=0))  # 前缀和的前缀和\n",
    "\n",
    "        ans = 0\n",
    "        for i, v in enumerate(strength):\n",
    "            l, r = left[i] + 1, right[i] - 1  # [l, r]  左闭右闭\n",
    "            tot = (i - l + 1) * (ss[r + 2] - ss[i + 1]) - (r - i + 1) * (ss[i + 1] - ss[l])\n",
    "            ans += v * tot  # 累加贡献\n",
    "        return ans % (10 ** 9 + 7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalStrength(self, strength: List[int]) -> int:\n",
    "        n = len(strength)\n",
    "        # left[i] 为左侧严格小于 strength[i] 的最近元素位置（不存在时为 -1）\n",
    "        # right[i] 为右侧小于等于 strength[i] 的最近元素位置（不存在时为 n）\n",
    "        left, right, st = [-1] * n, [n] * n, []\n",
    "        for i, v in enumerate(strength):\n",
    "            while st and strength[st[-1]] >= v: right[st.pop()] = i\n",
    "            if st: left[i] = st[-1]\n",
    "            st.append(i)\n",
    "\n",
    "        ss = list(accumulate(accumulate(strength, initial=0), initial=0))  # 前缀和的前缀和\n",
    "\n",
    "        ans = 0\n",
    "        for i, v in enumerate(strength):\n",
    "            l, r = left[i] + 1, right[i] - 1  # [l, r]  左闭右闭\n",
    "            tot = (i - l + 1) * (ss[r + 2] - ss[i + 1]) - (r - i + 1) * (ss[i + 1] - ss[l])\n",
    "            ans += v * tot  # 累加贡献\n",
    "        return ans % (10 ** 9 + 7)\n",
    "\n",
    "\n",
    "# def get_index(nums):\n",
    "#     min_index, n = 0, len(nums)\n",
    "#     min = nums[0]\n",
    "#     for i in range(n):\n",
    "#         if nums[i] < min:\n",
    "#             min = nums[i]\n",
    "#             min_index = i\n",
    "#     return min_index\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def totalStrength(self, strength: List[int]) -> int:\n",
    "#         n=len(strength)\n",
    "#         x_index = get_index(strength)\n",
    "#         x=strength[x_index]\n",
    "#         len_left = x_index\n",
    "#         sum_left = 0    \n",
    "#         for i in range(1,x_index):\n",
    "#             sum_left += strength[i] * i\n",
    "#         M = sum_left + len_left*x\n",
    "\n",
    "#         len_right=n-x_index-1\n",
    "#         sum_right=0\n",
    "#         for j in range(x_index, n):\n",
    "#             sum_right += strength[j] *(len_right-j)\n",
    "#         N=(sum_right+len_right*x)*x\n",
    "\n",
    "\n",
    "#         return x*(x+M +N+len_right*M+len_right *N-len_right*len_left*x)+func2(strength[:x_index])+func2(nums[x_index:])\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalStrength(self, strength: List[int]) -> int:\n",
    "        n = len(strength)\n",
    "        # left[i] 为左侧严格小于 strength[i] 的最近元素位置（不存在时为 -1）\n",
    "        # right[i] 为右侧小于等于 strength[i] 的最近元素位置（不存在时为 n）\n",
    "        left, right, st = [-1] * n, [n] * n, []\n",
    "        for i, v in enumerate(strength):\n",
    "            while st and strength[st[-1]] >= v: right[st.pop()] = i\n",
    "            if st: left[i] = st[-1]\n",
    "            st.append(i)\n",
    "\n",
    "        ss = list(accumulate(accumulate(strength, initial=0), initial=0))  # 前缀和的前缀和\n",
    "\n",
    "        ans = 0\n",
    "        for i, v in enumerate(strength):\n",
    "            l, r = left[i] + 1, right[i] - 1  # [l, r]  左闭右闭\n",
    "            tot = (i - l + 1) * (ss[r + 2] - ss[i + 1]) - (r - i + 1) * (ss[i + 1] - ss[l])\n",
    "            ans += v * tot  # 累加贡献\n",
    "        return ans % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalStrength(self, strength: List[int]) -> int:\n",
    "        stk = []\n",
    "        n = len(strength)\n",
    "        left = [-1] * n\n",
    "        for i in range(n):\n",
    "            while stk and strength[stk[-1]] >= strength[i]:\n",
    "                stk.pop()\n",
    "            if stk:\n",
    "                left[i] = stk[-1]\n",
    "            stk.append(i)\n",
    "\n",
    "        stk = []\n",
    "        right = [n] * n\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            # > 防止重复计计算\n",
    "            while stk and strength[stk[-1]] > strength[i]:\n",
    "                stk.pop()\n",
    "            if stk:\n",
    "                right[i] = stk[-1]\n",
    "            stk.append(i)\n",
    "\n",
    "        s = accumulate(strength, initial=1)\n",
    "        ss = list(accumulate(s, initial=0))\n",
    "\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            l, r = left[i] + 1, right[i] - 1\n",
    "            res += ((i-l+1) * (ss[r+2] - ss[i+1]) - (r-i+1) * (ss[i+1] - ss[l])) * strength[i]\n",
    "\n",
    "        return res % (10 ** 9 + 7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalStrength(self, strength: List[int]) -> int:\n",
    "        n = len(strength)\n",
    "        # left[i] 为左侧严格小于 strength[i] 的最近元素位置（不存在时为 -1）\n",
    "        # right[i] 为右侧小于等于 strength[i] 的最近元素位置（不存在时为 n）\n",
    "        left, right, st = [-1] * n, [n] * n, []\n",
    "        for i, v in enumerate(strength):\n",
    "            while st and strength[st[-1]] >= v: right[st.pop()] = i\n",
    "            if st: left[i] = st[-1]\n",
    "            st.append(i)\n",
    "\n",
    "        ss = list(accumulate(accumulate(strength, initial=0), initial=0))  # 前缀和的前缀和\n",
    "\n",
    "        ans = 0\n",
    "        for i, v in enumerate(strength):\n",
    "            l, r = left[i] + 1, right[i] - 1  # [l, r]  左闭右闭\n",
    "            tot = (i - l + 1) * (ss[r + 2] - ss[i + 1]) - (r - i + 1) * (ss[i + 1] - ss[l])\n",
    "            ans += v * tot  # 累加贡献\n",
    "        return ans % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalStrength(self, strength: List[int]) -> int:\n",
    "        n = len(strength)\n",
    "        # left[i] 为左侧严格小于 strength[i] 的最近元素位置（不存在时为 -1）\n",
    "        # right[i] 为右侧小于等于 strength[i] 的最近元素位置（不存在时为 n）\n",
    "        left, right, st = [-1] * n, [n] * n, []\n",
    "        for i, v in enumerate(strength):\n",
    "            while st and strength[st[-1]] >= v: right[st.pop()] = i\n",
    "            if st: left[i] = st[-1]\n",
    "            st.append(i)\n",
    "\n",
    "        ss = list(accumulate(accumulate(strength, initial=0), initial=0))  # 前缀和的前缀和\n",
    "\n",
    "        ans = 0\n",
    "        for i, v in enumerate(strength):\n",
    "            l, r = left[i] + 1, right[i] - 1  # [l, r]  左闭右闭\n",
    "            tot = (i - l + 1) * (ss[r + 2] - ss[i + 1]) - (r - i + 1) * (ss[i + 1] - ss[l])\n",
    "            ans += v * tot  # 累加贡献\n",
    "        return ans % (10 ** 9 + 7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalStrength(self, strength: List[int]) -> int:\n",
    "        n = len(strength)\n",
    "        # left[i] 为左侧严格小于 strength[i] 的最近元素位置（不存在时为 -1）\n",
    "        # right[i] 为右侧小于等于 strength[i] 的最近元素位置（不存在时为 n）\n",
    "        left, right, st = [-1] * n, [n] * n, []\n",
    "        for i, v in enumerate(strength):\n",
    "            while st and strength[st[-1]] >= v: right[st.pop()] = i\n",
    "            if st: left[i] = st[-1]\n",
    "            st.append(i)\n",
    "\n",
    "        ss = list(accumulate(accumulate(strength, initial=0), initial=0))  # 前缀和的前缀和\n",
    "\n",
    "        ans = 0\n",
    "        for i, v in enumerate(strength):\n",
    "            l, r = left[i] + 1, right[i] - 1  # [l, r]  左闭右闭\n",
    "            tot = (i - l + 1) * (ss[r + 2] - ss[i + 1]) - (r - i + 1) * (ss[i + 1] - ss[l])\n",
    "            ans += v * tot  # 累加贡献\n",
    "        return ans % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalStrength(self, strength: List[int]) -> int:\n",
    "        n = len(strength)\n",
    "        l, r = [-1] * n, [n] * n\n",
    "        st = []\n",
    "        for i, v in enumerate(strength):\n",
    "            while st and strength[st[-1]] >= v:\n",
    "                r[st.pop()] = i\n",
    "            if st:\n",
    "                l[i] = st[-1]\n",
    "            st.append(i)\n",
    "        presum = list(accumulate((accumulate(strength, initial = 0)),initial = 0))\n",
    "\n",
    "        res = 0\n",
    "        for i, v in enumerate(strength):\n",
    "            ll, rr = l[i] + 1, r[i] - 1\n",
    "            res += v*((presum[rr+2] - presum[i+1]) * (i-ll+1) - (presum[i+1] - presum[ll])*(rr - i+1))\n",
    "        return res % (10**9+7)\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalStrength(self, strength: List[int]) -> int:\n",
    "        n = len(strength)\n",
    "        # left[i] 为左侧严格小于 strength[i] 的最近元素位置（不存在时为 -1）\n",
    "        # right[i] 为右侧小于等于 strength[i] 的最近元素位置（不存在时为 n）\n",
    "        left, right, st = [-1] * n, [n] * n, []\n",
    "        for i, v in enumerate(strength):\n",
    "            while st and strength[st[-1]] >= v: right[st.pop()] = i\n",
    "            if st: left[i] = st[-1]\n",
    "            st.append(i)\n",
    "\n",
    "        ss = list(accumulate(accumulate(strength, initial=0), initial=0))  # 前缀和的前缀和\n",
    "\n",
    "        ans = 0\n",
    "        for i, v in enumerate(strength):\n",
    "            l, r = left[i] + 1, right[i] - 1  # [l, r]  左闭右闭\n",
    "            tot = (i - l + 1) * (ss[r + 2] - ss[i + 1]) - (r - i + 1) * (ss[i + 1] - ss[l])\n",
    "            ans += v * tot  # 累加贡献\n",
    "        return ans % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalStrength(self, strength: List[int]) -> int:\n",
    "        n = len(strength)\n",
    "        # left[i] 为左侧严格小于 strength[i] 的最近元素位置（不存在时为 -1）\n",
    "        # right[i] 为右侧小于等于 strength[i] 的最近元素位置（不存在时为 n）\n",
    "        left, right, st = [-1] * n, [n] * n, []\n",
    "        for i, v in enumerate(strength):\n",
    "            while st and strength[st[-1]] >= v: right[st.pop()] = i\n",
    "            if st: left[i] = st[-1]\n",
    "            st.append(i)\n",
    "\n",
    "        ss = list(accumulate(accumulate(strength, initial=0), initial=0))  # 前缀和的前缀和\n",
    "\n",
    "        ans = 0\n",
    "        for i, v in enumerate(strength):\n",
    "            l, r = left[i] + 1, right[i] - 1  # [l, r]  左闭右闭\n",
    "            tot = (i - l + 1) * (ss[r + 2] - ss[i + 1]) - (r - i + 1) * (ss[i + 1] - ss[l])\n",
    "            ans += v * tot  # 累加贡献\n",
    "        return ans % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalStrength(self, strength: List[int]) -> int:\n",
    "        n = len(strength)\n",
    "        left,right,st = [-1]*n, [n]*n, []\n",
    "        for i,v in enumerate(strength):\n",
    "            while st and strength[st[-1]]>v:\n",
    "                right[st.pop()] = i\n",
    "            if st: left[i] = st[-1]\n",
    "            st.append(i)\n",
    "        ss = list(accumulate(accumulate(strength, initial = 0), initial=0))\n",
    "        ans = 0 \n",
    "        for i,v in enumerate(strength):\n",
    "            l, r = left[i] + 1, right[i] - 1  # [l, r]  左闭右闭\n",
    "            tot = (i - l + 1) * (ss[r + 2] - ss[i + 1]) - (r - i + 1) * (ss[i + 1] - ss[l])\n",
    "            ans += v * tot  # 累加贡献\n",
    "        return ans % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalStrength(self, strength: List[int]) -> int:\n",
    "        p = int(1e9 + 7)\n",
    "        n = len(strength)\n",
    "        ps = [0] * (n + 1)\n",
    "        for i, v in enumerate(strength):\n",
    "            ps[i] = ps[i - 1] + v\n",
    "            if ps[i] >= p:\n",
    "                ps[i] -= p\n",
    "        sta = []\n",
    "        stas = 0\n",
    "        stav = 0\n",
    "        r = 0\n",
    "        for i, v in enumerate(strength):\n",
    "            cc = 1\n",
    "            ss = ps[i - 1]\n",
    "            while sta and v <= sta[-1][0]:\n",
    "                pv, pc, pss = sta.pop()\n",
    "                stav -= pv * pc\n",
    "                stas -= pss * pv\n",
    "                ss += pss\n",
    "                cc += pc\n",
    "            sta.append((v, cc, ss))\n",
    "            stav += v * cc\n",
    "            stas += ss * v\n",
    "            stav %= p\n",
    "            stas %= p\n",
    "            ss %= p\n",
    "            r += ps[i] * stav - stas\n",
    "            r %= p\n",
    "        return r\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalStrength(self, s: List[int]) -> int:\n",
    "        n = len(s)\n",
    "        left, right, st = [-1] * n, [n] * n, []\n",
    "        for i, x in enumerate(s):\n",
    "            while st and s[st[-1]] >= x:\n",
    "                right[st.pop()] = i\n",
    "            if st: left[i] = st[-1]\n",
    "            st.append(i)\n",
    "        ss = list(accumulate(accumulate(s, initial=0), initial=0))\n",
    "        ans = 0\n",
    "        for i, x in enumerate(s):\n",
    "            l, r = left[i] + 1, right[i] - 1\n",
    "            tot = (i - l + 1) * (ss[r+2] - ss[i+1]) - (r - i + 1) * (ss[i+1] - ss[l])\n",
    "            ans += tot * x\n",
    "        return ans % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalStrength(self, strength: List[int]) -> int:\n",
    "        res,n,mod = 0,len(strength),10**9+7\n",
    "        left,right = [-1]*n,[n]*n\n",
    "        sta = []\n",
    "        for i,num in enumerate(strength):\n",
    "            while sta and strength[sta[-1]]>num:\n",
    "                right[sta.pop()]=i\n",
    "            if sta: left[i]=sta[-1]\n",
    "            sta.append(i)\n",
    "        ss = list(accumulate(accumulate(strength,initial=0),initial=0))\n",
    "        print(left,right)\n",
    "        res = 0\n",
    "        for i,(s,l,r) in enumerate(zip(strength,left,right)):\n",
    "            l+=1\n",
    "            r-=1\n",
    "            res+=s*((i-l+1)*(ss[r+2]-ss[i+1])-(r-i+1)*(ss[i+1]-ss[l]))\n",
    "        return res%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9+7\n",
    "class Solution:\n",
    "    def totalStrength(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        pres = [0] * (n+1)\n",
    "        press = [0] * (n+2)\n",
    "        left = [-1] * n\n",
    "        right = [n] * n\n",
    "        stack = []\n",
    "        for i, x in enumerate(nums):\n",
    "            pres[i+1] = (pres[i] + x) % MOD\n",
    "            press[i+2] = (press[i+1] + pres[i+1]) % MOD\n",
    "            while stack and x < nums[stack[-1]]:\n",
    "                right[stack.pop()] = i\n",
    "            if stack:\n",
    "                left[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "\n",
    "        ans = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            l, r = left[i] + 1, right[i] - 1\n",
    "            print(i, l, r)\n",
    "            tot = (i - l + 1) * (press[r+2] - press[i+1]) % MOD - (r - i + 1) * (press[i+1] - press[l]) % MOD\n",
    "            ans += x * tot % MOD\n",
    "\n",
    "        return ans % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalStrength(self, s: List[int]) -> int:\n",
    "        n = len(s)\n",
    "        pref = [0] \n",
    "        mod = 10 ** 9 + 7\n",
    "        for i in range(n):\n",
    "            pref.append(pref[-1] + s[i])\n",
    "        prefpref = [0]\n",
    "        for i in range(n):\n",
    "            prefpref.append((prefpref[-1] + pref[i + 1]) % mod)\n",
    "        # print(\"pref\", pref)\n",
    "        # print(\"prefpref\", prefpref)\n",
    "\n",
    "        stk = [-1]\n",
    "        l = [0] * n \n",
    "        r = [n] * n\n",
    "        for i in range(n):\n",
    "            while len(stk) > 1 and s[stk[-1]] >= s[i]:\n",
    "                r[stk[-1]] = i\n",
    "                stk.pop()\n",
    "            l[i] = stk[-1]\n",
    "            stk.append(i)\n",
    "        # print(\"l\", l)\n",
    "        # print(\"r\", r)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            # print(i)\n",
    "            tmp = prefpref[i + 1] - prefpref[l[i] + 1]\n",
    "            # print(tmp)\n",
    "            tmp = pref[i + 1] * (i - l[i]) - tmp + (pref[i + 1] - pref[l[i] + 1])\n",
    "            rtmp = prefpref[r[i]] - prefpref[i + 1] - pref[i + 1] * (r[i] - i - 1)\n",
    "            # print(i, tmp, r[i] - i, rtmp, i - l[i], (tmp * (r[i] - i) + rtmp * (i - l[i]))* s[i])\n",
    "            ans = (ans + (tmp * (r[i] - i) + rtmp * (i - l[i]))* s[i]) % mod\n",
    "        return ans \n",
    "        # 14 * 2 + 6 * 2 = 40\n",
    "        # 213 - 25 - 36 = 152 // 4 = 38\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def totalStrength(self, strength: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "\n",
    "        n = len(strength)\n",
    "        left, st = [-1] * n, []  # left[i] 为左侧严格小于 strength[i] 的最近元素位置（不存在时为 -1）\n",
    "        for i, v in enumerate(strength):\n",
    "            while st and strength[st[-1]] >= v: st.pop()\n",
    "            if st: left[i] = st[-1]\n",
    "            st.append(i)\n",
    "\n",
    "        right, st = [n] * n, []  # right[i] 为右侧小于等于 strength[i] 的最近元素位置（不存在时为 n）\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while st and strength[st[-1]] > strength[i]: st.pop()\n",
    "            if st: right[i] = st[-1]\n",
    "            st.append(i)\n",
    "\n",
    "        s = [0] * (n + 1)  # 前缀和\n",
    "        for i, v in enumerate(strength):\n",
    "            s[i + 1] = (s[i] + v) % MOD\n",
    "        ss = [0] * (n + 2)  # 前缀和的前缀和\n",
    "        for i, v in enumerate(s):\n",
    "            ss[i + 1] = (ss[i] + v) % MOD\n",
    "\n",
    "        ans = 0\n",
    "        for i, v in enumerate(strength):\n",
    "            l, r = left[i] + 1, right[i] - 1  # [l, r]  左闭右闭\n",
    "            tot = ((i - l + 1) * (ss[r + 2] - ss[i + 1]) - (r - i + 1) * (ss[i + 1] - ss[l])) % MOD\n",
    "            ans = (ans + tot * v) % MOD  # 累加贡献\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalStrength(self, strength: List[int]) -> int:\n",
    "        p = int(1e9 + 7)\n",
    "        n = len(strength)\n",
    "        ps = [0] * (n + 1)\n",
    "        for i, v in enumerate(strength):\n",
    "            ps[i] = ps[i - 1] + v\n",
    "            if ps[i] >= p:\n",
    "                ps[i] -= p\n",
    "        sta = []\n",
    "        r = stas = stav = 0\n",
    "        for i, v in enumerate(strength):\n",
    "            cc = 1\n",
    "            ss = ps[i - 1]\n",
    "            while sta and v <= sta[-1][0]:\n",
    "                pv, pc, pss = sta.pop()\n",
    "                stav -= pv * pc\n",
    "                stas -= pss * pv\n",
    "                ss += pss\n",
    "                cc += pc\n",
    "            ss %= p\n",
    "            sta.append((v, cc, ss))\n",
    "            stav += v * cc\n",
    "            stas += ss * v\n",
    "            stav %= p\n",
    "            stas %= p\n",
    "            r += ps[i] * stav - stas\n",
    "            r %= p\n",
    "        return r\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalStrength(self, strength: List[int]) -> int:\n",
    "        MOD = 1000000007\n",
    "        n = len(strength)\n",
    "        left, right, stk = [-1] * n, [n] * n, []\n",
    "        for i, s in enumerate(strength):\n",
    "            while stk and strength[stk[-1]] >= s:\n",
    "                right[stk.pop()] = i\n",
    "            if stk:\n",
    "                left[i] = stk[-1]\n",
    "            stk.append(i)\n",
    "\n",
    "        ss = list(accumulate(accumulate(strength, initial=0), initial=0))\n",
    "        print(ss)\n",
    "        res = 0\n",
    "        for i, s in enumerate(strength):\n",
    "            l, r = left[i] + 1, right[i] - 1\n",
    "            tot = (i - l + 1) * (ss[r + 2] - ss[i + 1]\n",
    "                                 ) - (r - i + 1) * (ss[i + 1] - ss[l])\n",
    "            res += s * tot\n",
    "            res %= MOD\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalStrength(self, strength: List[int]) -> int:\n",
    "        n = len(strength)\n",
    "        p = strength[:]\n",
    "        for i in range(1, n):\n",
    "            p[i] += p[i - 1]\n",
    "        ss = [0]\n",
    "        for s in p:\n",
    "            ss.append(ss[-1] + s)\n",
    "        res = 0\n",
    "        stack = []\n",
    "        strength += [0]\n",
    "        for i in range(n + 1):\n",
    "            while stack and strength[stack[-1]] > strength[i]:\n",
    "                idx = stack.pop()\n",
    "                l = stack[-1] + 1 if stack else 0\n",
    "                r = i - 1 \n",
    "                res += strength[idx] * ((idx - l + 1) * (ss[r + 1] - ss[idx]) - (r - idx + 1) * (ss[idx] - (ss[l - 1] if l > 0 else 0)))\n",
    "            stack.append(i)\n",
    "        return res % (10 ** 9 + 7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalStrength(self, strength: List[int]) -> int:\n",
    "        n = len(strength)\n",
    "        p = strength[:]\n",
    "        for i in range(1, n):\n",
    "            p[i] += p[i - 1]\n",
    "        ss = [0]\n",
    "        for s in p:\n",
    "            ss.append(ss[-1] + s)\n",
    "        res = 0\n",
    "        stack = []\n",
    "        strength += [0]\n",
    "        for i in range(n + 1):\n",
    "            while stack and strength[stack[-1]] > strength[i]:\n",
    "                idx = stack.pop()\n",
    "                l = stack[-1] + 1 if stack else 0\n",
    "                r = i - 1 \n",
    "                res += strength[idx] * ((idx - l + 1) * (ss[r + 1] - ss[idx]) - (r - idx + 1) * (ss[idx] - (ss[l - 1] if l > 0 else 0)))\n",
    "            stack.append(i)\n",
    "        return res % (10 ** 9 + 7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalStrength(self, strength: List[int]) -> int:\n",
    "        n = len(strength)\n",
    "        p = strength[:]\n",
    "        for i in range(1, n):\n",
    "            p[i] += p[i - 1]\n",
    "        ss = [0]\n",
    "        for s in p:\n",
    "            ss.append(ss[-1] + s)\n",
    "        res = 0\n",
    "        stack = []\n",
    "        strength += [0]\n",
    "        for i in range(n + 1):\n",
    "            while stack and strength[stack[-1]] > strength[i]:\n",
    "                idx = stack.pop()\n",
    "                l = stack[-1] + 1 if stack else 0\n",
    "                r = i - 1 \n",
    "                res += strength[idx] * ((idx - l + 1) * (ss[r + 1] - ss[idx]) - (r - idx + 1) * (ss[idx] - (ss[l - 1] if l > 0 else 0)))\n",
    "            stack.append(i)\n",
    "        return res % (10 ** 9 + 7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import accumulate\n",
    "mod = 10**9 + 7\n",
    "class Solution:\n",
    "    def totalStrength(self, strength: List[int]) -> int:\n",
    "        a = [0] + strength + [0]\n",
    "        stk = []\n",
    "        P = [0] + list(accumulate(a))\n",
    "        PP = [0] + list(accumulate(P))\n",
    "        #   \\sum_{x=l}^{base} \\sum_{y=base}^{r}  sum(a[x,...,y])\n",
    "        #   \\sum_{x=l}^{base} \\sum_{y=base}^{r}  (P[y+1]-P[x])\n",
    "        #   \\sum_{x=l}^{base} \\sum_{y=base}^{r}  (P[y+1]) + \\sum_{x=l}^{base} \\sum_{y=base}^{r}  (-P[x])\n",
    "        #   (base-l+1) \\sum_{y=base}^{r}  (P[y+1]) - (r-base+1)\\sum_{x=l}^{base} (P[x])\n",
    "        #   (base-l+1) \\sum_{y=base+1}^{r+1}  (P[y]) - (r-base+1)\\sum_{x=l}^{base} (P[x])\n",
    "        #   (base-l+1) (PP[r+2]-PP[base+1]) - (r-base+1)(PP[base+1]- PP[l])\n",
    "        ans = 0\n",
    "\n",
    "\n",
    "        for i, v in enumerate(a):\n",
    "            while stk and a[stk[-1]] >= v:\n",
    "                base = stk.pop()\n",
    "                if stk:\n",
    "                    left = stk[-1]\n",
    "                    l = left + 1\n",
    "                    r = i - 1\n",
    "                    ans +=((base-l+1)*(PP[r+2]-PP[base+1]) - (r-base+1) * (PP[base+1]-PP[l]))*a[base]%mod\n",
    "            stk.append(i)\n",
    "        return ans % mod\n",
    "\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalStrength(self, strength: List[int]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        n = len(strength)\n",
    "        left = [-1]*n\n",
    "        right = [n]*n\n",
    "        pre_sum = [0]*(n+1) #前缀和\n",
    "        q =deque()\n",
    "        pp = [0]*(n+2) #前缀和的前缀和\n",
    "        for i in range(n):\n",
    "            pre_sum[i+1] = pre_sum[i] + strength[i] \n",
    "            pp[i+1] = pp[i]+pre_sum[i]\n",
    "        pp[n+1] = pp[n]+pre_sum[n]\n",
    "        for i,x in enumerate(strength):\n",
    "            while q and strength[q[-1]] >= x:  #左右边界，参考灵神题解，一次遍历。为了避免重复计算，一边取等，一边不取等。\n",
    "                k = q.pop()\n",
    "                right[k] = i\n",
    "            if q : left[i] = q[-1]\n",
    "            q.append(i)  \n",
    "        ans = 0            \n",
    "        for i in range(n):  # l+1,...,i-1,i,i+1,..., r-1\n",
    "            #  l+1 计算了1*(r-i)次，l+2计算了2*(r-i)次，，，i-1计算了(i-l-1)*(r-i)次\n",
    "            #  提出r-i ,上式等价于 计算 sum(l+1,i-1) +sum(l+2,i-1)+...+sum(i-1,i-1)   (此处sum是对nums求sum)\n",
    "            #                        = pre_sum[i] - pre_sum[l+1] + pre_sum(i)-pre_sum[l+2]+...+pre_sum[i] -pre_sum(i-1)  \n",
    "            #                        = (i-l+1)*pre_sum[i] - sum(l+1,i-1)       (此处sum是对pre_sum求sum)\n",
    "            #                        = (i-l+1)*pre_sum[i] - (pp[i]-pp[l+1])\n",
    "\n",
    "            l = left[i]\n",
    "            r = right[i]\n",
    "            cur = strength[i]*(\n",
    "                (r-i)*((i-l-1)*pre_sum[i]-pp[i]+pp[l+1]) +  #i左边\n",
    "                (i-l)*(pp[r+1]-pp[i+2]-(r-i-1)*pre_sum[i+1])+ #i右边\n",
    "            strength[i]*(r-i)*(i-l)) #单独计算i \n",
    "            ans += cur%mod\n",
    "            ans = ans%mod\n",
    "        return ans  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalStrength(self, strength: List[int]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        n = len(strength)\n",
    "        left = [-1]*n\n",
    "        right = [n]*n\n",
    "        pre_sum = [0]*(n+1)\n",
    "        q =deque()\n",
    "        pp = [0]*(n+2)\n",
    "        for i in range(n):\n",
    "            pre_sum[i+1] = pre_sum[i] + strength[i] \n",
    "            pp[i+1] = pp[i]+pre_sum[i]\n",
    "        pp[n+1] = pp[n]+pre_sum[n]\n",
    "        for i,x in enumerate(strength):\n",
    "            while q and strength[q[-1]] >= x :#left < cur\n",
    "                k = q.pop()\n",
    "                right[k] = i\n",
    "            if q : left[i] = q[-1]\n",
    "            q.append(i)  \n",
    "        ans = 0          \n",
    "        # x*  l+1  i  r-1    \n",
    "        for i in range(n): \n",
    "            #   \n",
    "            l = left[i]\n",
    "            r = right[i]\n",
    "            cur = strength[i]*((r-i)*((i-l-1)*pre_sum[i]-pp[i]+pp[l+1]) + (i-l)*(pp[r+1]-pp[i+2]-(r-i-1)*pre_sum[i+1])+strength[i]*(r-i)*(i-l))\n",
    "            ans += cur%mod\n",
    "            ans = ans%mod\n",
    "        return ans  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import accumulate\n",
    "\n",
    "class Solution:\n",
    "    def totalStrength(self, strength: List[int]) -> int:\n",
    "        MOD = int(1e9) + 7\n",
    "\n",
    "        n = len(strength)\n",
    "        left = [-1] * n\n",
    "        right = [n] * n\n",
    "        st = []\n",
    "\n",
    "        for i in range(n):\n",
    "            x = strength[i]\n",
    "\n",
    "            while st and strength[st[-1]] >= x:\n",
    "                right[st.pop()] = i\n",
    "\n",
    "            if st:\n",
    "                left[i] = st[-1]\n",
    "\n",
    "            st.append(i)\n",
    "\n",
    "        pres = list(accumulate(strength, initial=0))\n",
    "        prespres = list(accumulate(pres, initial=0))\n",
    "\n",
    "        ret = 0\n",
    "        \n",
    "        for i in range(n):\n",
    "            l = left[i] + 1\n",
    "            r = right[i] - 1\n",
    "\n",
    "            tot = (i - l + 1) * (prespres[r + 2] - prespres[i + 1]) - (r - i + 1) * (prespres[i + 1] - prespres[l])\n",
    "\n",
    "            ret += strength[i] * tot\n",
    "            ret %= MOD\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "kmod = 10**9 + 7\n",
    "class Solution:\n",
    "    def totalStrength(self, strength: List[int]) -> int:\n",
    "        n = len(strength)\n",
    "\n",
    "        left = [-1] * n\n",
    "        s = []\n",
    "        for i in range(n):\n",
    "            while s and strength[s[-1]] > strength[i]:\n",
    "                s.pop()\n",
    "            if s:\n",
    "                left[i] = s[-1]\n",
    "            s.append(i)\n",
    "\n",
    "        right = [n] * n\n",
    "        s = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while s and strength[s[-1]] >= strength[i]:\n",
    "                s.pop()\n",
    "            if s:\n",
    "                right[i] = s[-1]\n",
    "            s.append(i)\n",
    "        \n",
    "        ans = 0\n",
    "        ps = list(accumulate(strength, initial=0))\n",
    "        pss = list(accumulate(ps, initial=0))\n",
    "        for i in range(n):\n",
    "            l, r = left[i], right[i]\n",
    "            # res = 0\n",
    "            # for a in range(l + 1, i + 1):\n",
    "            #     for b in range(i, r):\n",
    "            #         res += ps[b + 1] - ps[a]\n",
    "            res = (pss[r + 1] - pss[i + 1]) * (i - l) - (pss[i + 1] - pss[l + 1]) * (r - i)\n",
    "            ans += res * strength[i]\n",
    "            ans %= kmod\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalStrength(self, strength: List[int]) -> int:\n",
    "        s = list(accumulate(strength,initial=0))\n",
    "        ss = list(accumulate(s,initial=0))\n",
    "        n,mod = len(strength),1000000007\n",
    "        left,right,st = [-1]*n,[n]*n,[]\n",
    "        for i,x in enumerate(strength):\n",
    "            while st and strength[st[-1]] > x:\n",
    "                right[st.pop()] = i\n",
    "            if st: left[i] = st[-1]\n",
    "            st.append(i)\n",
    "        return sum(x*((i-l)*(ss[r+1]-ss[i+1])-(r-i)*(ss[i+1]-ss[l+1]))%mod for i,(x,l,r) in enumerate(zip(strength,left,right))) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalStrength(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        pre = [-1] * n\n",
    "        nxt = [n] * n\n",
    "\n",
    "        s = []\n",
    "        for i, x in enumerate(arr):\n",
    "            while s and x < arr[s[-1]]:\n",
    "                nxt[s.pop()] = i\n",
    "            if s:\n",
    "                pre[i] = s[-1]\n",
    "            s.append(i)\n",
    "\n",
    "        ans = 0\n",
    "        pre_sum = list(accumulate(arr, initial = 0))\n",
    "        pp_sum = list(accumulate(pre_sum, initial = 0))\n",
    "        for i, x in enumerate(arr):\n",
    "            l, r = pre[i], nxt[i]\n",
    "            t = (i-l)*(pp_sum[r+1]-pp_sum[i+1]) - (r-i)*(pp_sum[i+1]-pp_sum[l+1])\n",
    "            ans += t * x\n",
    "        return ans % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "kmod = 10**9 + 7\n",
    "class Solution:\n",
    "    def totalStrength(self, strength: List[int]) -> int:\n",
    "        n = len(strength)\n",
    "        ps = list(accumulate(strength, initial=0))\n",
    "\n",
    "        left = [-1] * n\n",
    "        s = []\n",
    "        for i in range(n):\n",
    "            while s and strength[s[-1]] > strength[i]:\n",
    "                s.pop()\n",
    "            if s:\n",
    "                left[i] = s[-1]\n",
    "            s.append(i)\n",
    "\n",
    "        right = [n] * n\n",
    "        s = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while s and strength[s[-1]] >= strength[i]:\n",
    "                s.pop()\n",
    "            if s:\n",
    "                right[i] = s[-1]\n",
    "            s.append(i)\n",
    "        \n",
    "        ans = 0\n",
    "        pss = list(accumulate(ps, initial=0))\n",
    "        for i in range(n):\n",
    "            l, r = left[i], right[i]\n",
    "            res = (pss[r + 1] - pss[i + 1]) * (i - l) - (pss[i + 1] - pss[l + 1]) * (r - i)\n",
    "            ans += res * strength[i]\n",
    "            ans %= kmod\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalStrength(self, arr: List[int]) -> int:\n",
    "        # stack\n",
    "        # prefixsum\n",
    "        n = len(arr)\n",
    "        preSum = [0]\n",
    "        for val in arr:\n",
    "            tmp = preSum[-1] + val\n",
    "            preSum.append(tmp)\n",
    "\n",
    "\n",
    "        left = [-1] * n\n",
    "        # find smaller val than cur val\n",
    "        right = [n] * n\n",
    "        # find bigger or equal than cur val\n",
    "        stack = []\n",
    "        for i, num in enumerate(arr):\n",
    "            while stack and num <= arr[stack[-1]]:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                left[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "            \n",
    "        \n",
    "        stack = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while stack and arr[i] < arr[stack[-1]]:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                right[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "            \n",
    "        # res = 0\n",
    "        # print (preSum)\n",
    "        # for i, (x, l, r) in enumerate(zip(arr, left, right)):\n",
    "        #     tmp = 0\n",
    "        #     # print (l, r, i)\n",
    "        #     for j in range(l + 2, r + 1):\n",
    "        #         # -1 2 \n",
    "        #         # 0 1\n",
    "        #         # l + 1 + 1, r - 1 + 1\n",
    "        #         # 0 1 \n",
    "        #         diff = preSum[j] - preSum[l + 1]\n",
    "        #         # print (tmp, diff, preSum[j], preSum[l + 1])\n",
    "        #         tmp += diff\n",
    "        #     print (res, i, tmp)\n",
    "        #     res += x * tmp\n",
    "        \n",
    "        # return res % (10 ** 9 + 7)\n",
    "\n",
    "        ss = list(accumulate(accumulate(arr, initial=0), initial=0))  # 前缀和的前缀和\n",
    "        ans = 0\n",
    "        for i, v in enumerate(arr):\n",
    "            l, r = left[i] + 1, right[i] - 1  # [l, r]  左闭右闭\n",
    "\n",
    "            tot = (i - l + 1) * (ss[r + 2] - ss[i + 1]) - (r - i + 1) * (ss[i + 1] - ss[l])\n",
    "            ans += v * tot  # 累加贡献\n",
    "        return ans % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalStrength(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        post = [n - 1] * n  # 这里可以是n/n-1/null，取决于用途\n",
    "        pre = [0] * n  # 这里可以是0/-1/null，取决于用途\n",
    "        stack = []\n",
    "        for i in range(n):  # 这里也可以是从n-1到0倒序计算，取决于用途\n",
    "            while stack and nums[stack[-1]] > nums[i]:  # 这里可以是\"<\" \">\" \"<=\" \">=\"，取决于需要判断的大小关系\n",
    "                post[stack.pop()] = i - 1  # 这里可以是i或者i-1，取决于是否包含i作为右端点\n",
    "            if stack:  # 这里不一定可以同时计算，比如前后都是大于等于时，只有前后所求范围互斥时，可以计算\n",
    "                pre[i] = stack[-1] + 1  # 这里可以是stack[-1]或者stack[-1]+1，取决于是否包含stack[-1]作为左端点\n",
    "            stack.append(i)\n",
    "        mod = 10**9 + 7\n",
    "        s = list(accumulate(nums, initial=0))\n",
    "        ss = list(accumulate(s, initial=0))\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            left = pre[i]\n",
    "            right = post[i]\n",
    "            ans += nums[i]*((i-left+1)*(ss[right+2]-ss[i+1]) - (right-i+1)*(ss[i+1]-ss[left]))\n",
    "            ans %= mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalStrength(self, s: List[int]) -> int:\n",
    "        mod=10**9+7\n",
    "        n=len(s)\n",
    "        left=[-1]*(n+1)\n",
    "        right=[n]*(n+1)\n",
    "\n",
    "        #单调栈看看每个数作为最小值的范围\n",
    "        stack=[-1]\n",
    "        for i,v in enumerate(s+[0]):\n",
    "            while len(stack)>1 and s[stack[-1]]>v:\n",
    "                j=stack.pop()\n",
    "                left[j]=stack[-1]+1\n",
    "                right[j]=i-1\n",
    "            stack.append(i)\n",
    "        \n",
    "        # print(left,right)\n",
    "\n",
    "\n",
    "        # 计算前缀和的前缀和\n",
    "        pre=[0]+list(accumulate(s))\n",
    "        pre=[0]+list(accumulate(pre))\n",
    "        # print(pre)\n",
    "\n",
    "        \n",
    "        res=0\n",
    "        for i in range(n):\n",
    "            L=left[i]\n",
    "            R=right[i]\n",
    "            v=(i-L+1)*(pre[R+2]-pre[i+1])-(R-i+1)*(pre[i+1]-pre[L])\n",
    "            u=s[i]\n",
    "            res+=u*v%mod\n",
    "            # print(i,L,R,(i-L+1)*(pre[R+2]-pre[i+1])-(R-i+1)*(pre[i+1]-pre[L]))\n",
    "\n",
    "        return res%mod\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "def lowbit(x):\n",
    "    return x&-x\n",
    "class BIT:\n",
    "    def __init__(self,n):\n",
    "        self.F = [0] * n\n",
    "        self.n = n\n",
    "        \n",
    "    def update(self,pos,val):\n",
    "        while pos < self.n:\n",
    "            self.F[pos] += val\n",
    "            self.F[pos] %= MOD\n",
    "            pos += lowbit(pos)\n",
    "        return\n",
    "    \n",
    "    def query(self,pos):\n",
    "        res = 0\n",
    "        while pos:\n",
    "            res += self.F[pos]\n",
    "            pos -= lowbit(pos)\n",
    "        return res % MOD\n",
    "    \n",
    "    def qab(self,a,b):\n",
    "        return self.query(b+1)-self.query(a)\n",
    "    \n",
    "class Solution:\n",
    "    def totalStrength(self, strength: List[int]) -> int:\n",
    "        lpre,rpre,n = 0,0,len(strength)\n",
    "        L = []\n",
    "        R = []\n",
    "        for idx,i in enumerate(strength):\n",
    "            L.append((lpre + i*(idx+1))%MOD)\n",
    "            lpre = L[-1]\n",
    "            R.append((rpre + strength[n-idx-1]*(idx+1))%MOD)\n",
    "            rpre = R[-1]\n",
    "        R.reverse()\n",
    "        T = BIT(n+1)\n",
    "        for idx,i in enumerate(strength):\n",
    "            T.update(idx+1,i)\n",
    "        \n",
    "        res = 0\n",
    "        left,right = [0] * n,[0] * n\n",
    "        st = []\n",
    "        for idx,i in enumerate(strength):\n",
    "            end = idx\n",
    "            while st and st[-1][0] > i:\n",
    "                oi,oidx = st.pop()\n",
    "                right[oidx] = end\n",
    "            left[idx] = st[-1][1] if st else -1\n",
    "            st.append([i,idx])\n",
    "        for i in st:\n",
    "            right[i[1]] = n\n",
    "        # print(left)\n",
    "        # print(right)\n",
    "        \n",
    "\n",
    "        for i in range(n):\n",
    "            pr,nx = left[i],right[i]\n",
    "            ll,rr = i-pr,nx-i\n",
    "            pminus = 0 if pr == -1 else L[pr]\n",
    "            nminus = 0 if nx == n else R[nx]\n",
    "            A = (L[i] - pminus - (pr+1) * T.qab(pr+1,i))*rr\n",
    "            B = (R[i] - nminus - (n-nx) * T.qab(i,nx-1))*ll\n",
    "            res += (A + B - strength[i]*(rr*ll))*strength[i]\n",
    "            res %= MOD\n",
    "        return res\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalStrength(self, arr: List[int]) -> int:\n",
    "        N = len(arr)\n",
    "        stack = []\n",
    "        left = [0] * len(arr)\n",
    "        for i in range(len(arr)):\n",
    "            while stack and arr[stack[-1]] > arr[i]:\n",
    "                stack.pop()\n",
    "            left[i] = left[stack[-1]]+(i-stack[-1])*arr[i] if stack else (i+1)*arr[i]\n",
    "            stack.append(i)\n",
    "\n",
    "        stack = []\n",
    "        right = [0] * len(arr)\n",
    "        for i in range(len(arr)-1,-1,-1):\n",
    "            while stack and arr[stack[-1]] > arr[i]:\n",
    "                stack.pop()\n",
    "            right[i] = right[stack[-1]]+(stack[-1]-i)*arr[i] if stack else (N-i)*arr[i]\n",
    "            stack.append(i)\n",
    "\n",
    "        leftAcc = [0] + list(itertools.accumulate(left))\n",
    "        rightAcc = [0] + list(itertools.accumulate(reversed(right)))\n",
    "\n",
    "        total, ans = leftAcc[-1], 0\n",
    "        for i in range(N):\n",
    "            ans += (total - leftAcc[i] - rightAcc[N-(i+1)])*arr[i]\n",
    "        return ans % int(1e9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalStrength(self, strength: List[int]) -> int:\n",
    "        M = 10**9 +7\n",
    "        mins = [[0, 0, 0]]\n",
    "        last = res = 0\n",
    "        accu = list(accumulate(chain([0], strength)))\n",
    "        accu2 = list(accumulate(accu))\n",
    "        for i, n in enumerate(strength, 1):\n",
    "            while n < mins[-1][0]:\n",
    "                lastMin, r, _ = mins.pop()\n",
    "                x = r - mins[-1][1]\n",
    "                last += x*n*n+(n-lastMin)*(x*accu[i-1] - accu2[r-1]+ (accu2[r-x-1] if r -x -1 >= 0 else 0))\n",
    "            last += n * mins[-1][-1]\n",
    "            if n == mins[-1][0]:\n",
    "                mins[-1][2] += (i - mins[-1][1])*mins[-1][0]\n",
    "                mins[-1][1] = i\n",
    "            else:\n",
    "                mins.append([n, i, mins[-1][-1] + n*(i-mins[-1][1])])\n",
    "            last = (last + n*n) % M\n",
    "            res = (res + last) % M\n",
    "        return res \n",
    "        #\n",
    "        # Min[l,r]*(x*Accu[r]-Accu[l-1]-...Accu[l-1+x])\n",
    "        # 1) S[n]*(x*Accu[r]+x*S[n]- Accu[l-1]- ..Accu[l-1+x]) # x*S[n]*S[n]+(S[n]-Min[l,r])*(x*Accu[r]-Accu[l-1]-...Accu[l-1+x])\n",
    "        # 2) Min[l,r+1]*(Accu[r+S[n]-Accu[l-1]]) # Min[l,r]*S[n]\n",
    "        # V[n] = S[n]*S[n] + V[n-1]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
